class Solution
{
    bool check[301][301];
    int n = 0, m = 0;
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int ret = 0;
        n = grid.size();
        m = grid[0].size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] == '1' && !check[i][j])
                {
                    dfs(grid, i, j);
                    ++ret;
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<char>>& grid, int row, int col)
    {
        check[row][col] = true;
        if (row - 1 >= 0 && !check[row - 1][col] && grid[row - 1][col] == '1')
        {
            dfs(grid, row - 1, col);
        }
        if (row + 1 < n && !check[row + 1][col] && grid[row + 1][col] == '1')
        {
            dfs(grid, row + 1, col);
        }
        if (col - 1 >= 0 && !check[row][col - 1] && grid[row][col - 1] == '1')
        {
            dfs(grid, row, col - 1);
        }
        if (col + 1 < m && !check[row][col + 1] && grid[row][col + 1] == '1')
        {
            dfs(grid, row, col + 1);
        }
    }
};